package day_2022_4_to_7.nowcoder;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
/**
 * 重建二叉树
 * @author haomin
 * @date 2022/04/09 18:15
 **/
public class BuildTreeByPreAndIn {
    private int index = 0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return reConstructBinaryTreeHelper(pre,vin,0,pre.length -1);
    }

    private TreeNode reConstructBinaryTreeHelper(int[] pre, int[] vin, int left, int right) {
        if(left > right){
            return null;
        }
        if(index > pre.length){
            return null;
        }

        TreeNode root = new TreeNode(pre[index]);
        index++ ;

        int post = find(root,vin);
        root.left = reConstructBinaryTreeHelper(pre,vin,left,post - 1);
        root.right = reConstructBinaryTreeHelper(pre,vin,post + 1,right);
        return root;
    }

    private int find(TreeNode root, int[] vin) {
        for (int i = 0; i < vin.length; i++) {
            if(root.val == vin[i]){
                return i;
            }
        }
        return -1;
    }
}